package graph.weighted.shortestPath;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

import graph.weighted.CandyWeightedGraph;

/**
 * 
 * @Title: CandyDijkstra.java 
 * @Package graph.weighted.shortestPath 
 * @Description: 使用迪杰斯特拉算法求解带权图的最短路径长度
 *                  1、基于v1使用优先队列优化每一次循环中寻找距离顶点s最短的顶点的过程
 * @author CandyWall   
 * @date 2021年1月20日 下午10:48:14 
 * @version V1.0
 */
public class CandyDijkstra_v2 {
    private CandyWeightedGraph graph;
    private int s;
    private int[] distances;
    private boolean[] visited;  // 记录每个顶点是否已经确认了顶点s到它的距离已经找到最小值了
    
    public CandyDijkstra_v2(CandyWeightedGraph graph, int s) {
        this.graph = graph;
        graph.validateVertex(s);
        this.s = s;
        distances = new int[graph.getVertex_num()];
        Arrays.fill(distances, Integer.MAX_VALUE);
        // 从顶点s到自己本身的距离就是0
        distances[s] = 0;
        visited = new boolean[graph.getVertex_num()];
        dijkstra();
    }
    
    private class Node implements Comparable<Node> {
        private int v;
        private int dis;
        
        public int getV() {
            return v;
        }

        public int getDis() {
            return dis;
        }

        public Node(int v, int dis) {
            this.v = v;
            this.dis = dis;
        }

        @Override
        public int compareTo(Node o) {
            return this.dis - o.dis;
        }
    }
    
    /**
     * 使用迪杰斯特拉算法求解顶点s到其他各个顶点最短路径长度
     */
    private void dijkstra() {
        Queue<Node> queue = new PriorityQueue<Node>();
        queue.add(new Node(s, 0));
        // 如果所有顶点都已经确认它们各自到顶点s的距离已经是最小路径了，就退出循环
        while(!queue.isEmpty()) {
            // 找到当前没有被确认的顶点中，到顶点s距离最短的顶点，记录顶点编号和它到顶点s的距离
            int curV = queue.remove().getV();
            // 如果某个顶点已经被确认过到s的距离已经求出最小值了，
            // 那么就不用继续关于这个点进行后续更新操作了，进入下一次循环
            // 反之进行更新操作
            if(visited[curV]) {
                continue;
            }
            visited[curV] = true;
            // 尝试从curV顶点出发，去往相邻的顶点w，看看路径是否比当前顶点w到顶点s的路径要短，
            // 如果更短，就更新顶点w到顶点s的距离
            for(int w : graph.adjacentVertexes(curV)) {
                if(!visited[w]) {
                    int newDis = distances[curV] + graph.getWeight(curV, w);
                    if(newDis < distances[w]) {
                        distances[w] = newDis;
                        // 可能会导致相同顶点有多个Node，但是不影响最后取出的是某个顶点到s距离的最小值
                        queue.add(new Node(w, newDis));
                    }
                }
            }
        }
    }

    /**
     * 获取顶点s到顶点t的最短路径长度
     * @return
     */
    public int getShortestPath(int t) {
        graph.validateVertex(t);
        if(isConnectedTo(t)) {
            return distances[t];
        }
        return -1;
    }

    /**
     * 获取顶点s到其他各个顶点的距离
     * @return
     */
    public int[] getDistances() {
        return distances;
    }
    
    /**
     * 判断顶点t和顶点s是否连通
     * @param t
     * @return
     */
    public boolean isConnectedTo(int t) {
        graph.validateVertex(t);
        return visited[t];
    }

    public static void main(String[] args) {
        CandyWeightedGraph graph = new CandyWeightedGraph("testData/weightedGraph/shortestPath/Dijkstra/graph.txt");
        CandyDijkstra_v2 dijkstra = new CandyDijkstra_v2(graph, 0);
        System.out.println(Arrays.toString(dijkstra.getDistances()));
        System.out.println(dijkstra.getShortestPath(4));
    }

}
